"""
难度：简单
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
"""
from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return 0
        left = self.searchLeft(nums,target)
        right = self.searchRight(nums,target)
        if left == -1:
            return 0
        return right - left +1
    
    def searchRight(self,nums,target):
        left,right = 0, len(nums)-1
        while left < right:
            mid = left +(right-left+1)//2
            if nums[mid] <= target:
                left =mid
            else:
                right = mid-1
        return left
    def searchLeft(self,nums,target):
        left , right = 0,len(nums)-1
        while left < right:
            mid = left +(right-left)//2
            if nums[mid] < target:
                left = mid +1
            else: 
                right = mid
        if nums[left] == target:
            return left
        else:
            return -1
        